0117. 填充每个节点的下一个右侧节点指针 II【中等】
1. 📝 题目描述
给定一个二叉树:
struct Node { int val; Node *left; Node *right; Node *next; }
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
初始状态下,所有 next 指针都被设置为 NULL。
示例 1:

txt
输入:root = [1,2,3,4,5,null,7]
输出:[1,#,2,3,#,4,5,7,#]
解释:
给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。
序列化输出按层序遍历顺序(由 next 指针连接),'#' 表示每层的末尾。1
2
3
4
5
6
2
3
4
5
6
示例 2:
txt
输入:root = []
输出:[]1
2
2
提示:
- 树中的节点数在范围
[0, 6000]内 -100 <= Node.val <= 100
进阶:
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求,本题中递归程序的隐式栈空间不计入额外空间复杂度。
2. 🎯 s.1 - 虚拟头节点逐层串联
c
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *left;
* struct Node *right;
* struct Node *next;
* };
*/
struct Node* connect(struct Node* root) {
struct Node* cur = root;
while (cur) {
struct Node dummy;
dummy.next = NULL;
struct Node* tail = &dummy;
while (cur) {
if (cur->left) { tail->next = cur->left; tail = tail->next; }
if (cur->right) { tail->next = cur->right; tail = tail->next; }
cur = cur->next;
}
cur = dummy.next; // 进入下一层
}
return root;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
js
/**
* // Definition for a _Node.
* function _Node(val, left, right, next) {
* this.val = val === undefined ? null : val;
* this.left = left === undefined ? null : left;
* this.right = right === undefined ? null : right;
* this.next = next === undefined ? null : next;
* };
*/
/**
* @param {_Node} root
* @return {_Node}
*/
var connect = function (root) {
let cur = root
while (cur) {
const dummy = new _Node(0) // 下一层的虚拟头节点
let tail = dummy
while (cur) {
if (cur.left) {
tail.next = cur.left
tail = tail.next
}
if (cur.right) {
tail.next = cur.right
tail = tail.next
}
cur = cur.next
}
cur = dummy.next // 进入下一层
}
return root
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
py
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Node') -> 'Node':
cur = root
while cur:
dummy = Node(0) # 下一层的虚拟头节点
tail = dummy
while cur:
if cur.left:
tail.next = cur.left
tail = tail.next
if cur.right:
tail.next = cur.right
tail = tail.next
cur = cur.next
cur = dummy.next # 进入下一层
return root1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
- 时间复杂度:
,其中 是节点数,每个节点恰好访问一次 - 空间复杂度:
,只使用常数级指针变量
算法思路:
- 与 0116 不同,本题的二叉树不是完美二叉树,不能直接假设左右子都存在
- 用虚拟头节点
dummy在当前层遍历时,将下一层的所有子节点通过next串联起来 tail指针跟踪下一层链表的末尾,依次链接cur.left和cur.right- 遍历完当前层后,
cur = dummy.next进入下一层,重复直到没有下一层